/*
1475. 商品折扣后的最终价格
https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/
中等 2024/12/04
*/

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int>st;
        st.push(0);
        for(int i=1;i<prices.size();i++)
        {
            if(prices[st.top()]<prices[i]) st.push(i);
            else
            {
                while(!st.empty()&&prices[st.top()]>=prices[i])
                {
                    int k=st.top();
                    st.pop();
                    prices[k]-=prices[i];
                }
                st.push(i);
            }
        }
        return prices;

    }
};
